package swardToOffer.method_3_backtracking;

/**
 * @Author ChanZany
 * @Date 2021/5/20 17:30
 * @Version 1.0
 */
// 面试题13：机器人的运动范围
// 题目：地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动，它
// 每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和
// 大于k的格子。例如，当k为18时，机器人能够进入方格(35, 37)，因为3+5+3+7=18。
// 但它不能进入方格(35, 38)，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
public class RobotMove {
    //机器人从(0,0)开始出发，只能向右或下进行移动
    public int dfs(int m, int n, int x, int y, int k) {
        if (!check(m - 1, n - 1, x, y, k)) return 0;
        return 1 + dfs(m, n, x + 1, y, k) + dfs(m, n, x, y + 1, k);
    }

    //检查该坐标的方格能否进入
    private boolean check(int xLen, int yLen, int x, int y, int k) {
        if (x < 0 || y < 0 || x > xLen || y > yLen) return false;
        int sum = x % 10 + (x / 10) % 10 + (x / 100) % 10 + y % 10 + (y / 10) % 10 + (y / 100) % 10;
        return (sum <= k);
    }

    public static void main(String[] args) {
        RobotMove robotMove = new RobotMove();
        System.out.println(robotMove.dfs(3, 1, 0, 0, 0));
    }
}
